Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]] Output: 12
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
Average Rating: 4.19 (47 votes)
Summary
We have to find the minimum sum of numbers over a path from the top left to the bottom right of the given matrix .
Solution
Approach 1: Brute Force
The Brute Force approach involves recursion. For each element, we consider two paths, rightwards and downwards and find the minimum sum out of those two. It specifies whether we need to take a right step or downward step to minimize the sum.
cost(i,j)=grid[i][j]+min(cost(i+1,j),cost(i,j+1))
Complexity Analysis
- Time complexity : O(2m+n). For every move, we have atmost 2 options.
- Space complexity : O(m+n). Recursion of depth m+n.
Approach 2: Dynamic Programming 2D
Algorithm
We use an extra matrix dp of the same size as the original matrix. In this matrix, dp(i,j) represents the minimum sum of the path from the index (i,j) to the bottom rightmost element. We start by initializing the bottom rightmost element of dp as the last element of the given matrix. Then for each element starting from the bottom right, we traverse backwards and fill in the matrix with the required minimum sums. Now, we need to note that at every element, we can move either rightwards or downwards. Therefore, for filling in the minimum sum, we use the equation:
dp(i,j)=grid(i,j)+min(dp(i+1,j),dp(i,j+1))
taking care of the boundary conditions.
The following figure illustrates the process:
Complexity Analysis
-
Time complexity : O(mn). We traverse the entire matrix once.
-
Space complexity : O(mn). Another matrix of the same size is used.
Approach 3: Dynamic Programming 1D
Algorithm
In the previous case, instead of using a 2D matrix for dp, we can do the same work using a dp array of the row size, since for making the current entry all we need is the dp entry for the bottom and the right element. Thus, we start by initializing only the last element of the array as the last element of the given matrix. The last entry is the bottom rightmost element of the given matrix. Then, we start moving towards the left and update the entry dp(j) as:
dp(j)=grid(i,j)+min(dp(j),dp(j+1))
We repeat the same process for every row as we move upwards. At the end dp(0) gives the required minimum sum.
Complexity Analysis
-
Time complexity : O(mn). We traverse the entire matrix once.
-
Space complexity : O(n). Another array of row size is used.
Approach 4: Dynamic Programming (Without Extra Space)
Algorithm
This approach is same as Approach 2, with a slight difference. Instead of using another dp matrix. We can store the minimum sums in the original matrix itself, since we need not retain the original matrix here. Thus, the governing equation now becomes:
grid(i,j)=grid(i,j)+min(grid(i+1,j),grid(i,j+1))
Complexity Analysis
-
Time complexity : O(mn). We traverse the entire matrix once.
-
Space complexity : O(1). No extra space is used.
July 10, 2019 8:48 AM
Approach 4 can be more readable:
int m = grid.length, n = grid[0].length;
for(int i = 1; i < m; ++i) grid[i][0] += grid[i - 1][0];
for(int j = 1; j < n; ++j) grid[0][j] += grid[0][j - 1];
for(int i = 1; i < m; ++i){
for(int j = 1; j < n; ++j){
grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
}
}
return grid[m-1][n-1];March 10, 2018 9:08 PM
Dijkstra might be overkill here, but it also works.
January 4, 2020 2:50 PM
I don't think modify the original matrix is a good idea
July 4, 2019 11:01 PM
The reason why DP works here (but not in an actual shortest distance problem) is because we can only move right and down through the matrix. If we can move in all 4 directions, DP would give the wrong answer.
March 20, 2020 8:41 AM
why're we starting at the bottom right corner?
February 10, 2020 6:07 PM
Interesting that we have the restriction on the input values of non-negative numbers.
The DP solution apparently works for negative numbers as well.
Last Edit: September 16, 2019 7:32 AM
Shouldn't the complexity of first approach be O(2M*N). Why (M+N)?
are we allowed to move up or move to the left in this problem?
overwriting the inputs, how is that O(1) space? I was asked in some interviews specifically that inputs are read only! please correct me if my understanding is not right, thanks.
A Java solution that runs from the top-left to bottom-right:
public int minPathSum(int[][] grid) {
int m = grid.length + 1;
int n = grid[0].length + 1;
int[][] dp = new int[m][n];
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
if(j==1)
dp[i][j] = dp[i-1][j] + grid[i-1][j-1];
else if (i==1)
dp[i][j] = dp[i][j-1] + grid[i-1][j-1];
else
dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i-1][j-1];
}
}
return dp[m-1][n-1];
}
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 03/25/2021 12:58 | Accepted | 8 ms | 9.7 MB | cpp |
xxxxxxxxxxclass Solution {public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if (i == 0 && j != 0) grid[i][j] = grid[i][j] + grid[i][j - 1]; else if (i != 0 && j == 0) grid[i][j] = grid[i][j] + grid[i - 1][j]; else if (i == 0 && j == 0) grid[i][j] = grid[i][j]; else grid[i][j] = min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j]; } } return grid[m-1][n-1]; }};